package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * LeafSimilar
 * 872. 叶子相似的树
 * https://leetcode.cn/problems/leaf-similar-trees/
 *
 * @author: lupeng6
 * @create: 2021/5/10 14:24
 */
public class LeafSimilar {


    public static void main(String[] args) {

    }


    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();

        getLeaves(root1, l1);
        getLeaves(root2, l2);

        if (l1.size() != l2.size()) {
            return false;
        }

        for (int i = 0; i < l1.size(); i++) {
            if (!l1.get(i).equals(l2.get(i))) {
                return false;
            }
        }
        return true;
    }


    private void getLeaves(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            list.add(node.val);
        }
        getLeaves(node.left, list);
        getLeaves(node.right, list);
    }
}
